iT邦幫忙

2021 iThome 鐵人賽

DAY 8
1

先來看簡述題目的定義

  1. 至少要有連續3個以上的整數
  2. 從左往右看他要是嚴格遞增直到這些數中的最大值(山頂),而後嚴格遞減

看完以上兩點,理所當然可以推論山頂不會在陣列的第一個數和最後一個數

Input: arr = [2,1,4,7,3,2,5]

以這個例子來說

這裡的山就是 [ 1, 4, 7, 3, 2]

符合

  1. 陣列長度 > 3,其中 7 就是山頂

  2. 1 < 4 < 7 和 7 > 3 > 2

應該大多數人看到題目的想法都是:
開始由左往右檢查,數字是否有嚴格遞增或是嚴格遞減的情況,並且追蹤目前最高的數值,以及目前山最長的長度,然後就開始嘗試實作程式碼,越寫越覺得有些地方沒有注意到,或是遇到一些情況時要額外處理,實作上變得很複雜。

今天想在這裡分享一個看起來不錯的解決方式。
既然我們要找出最長的山,我們應該要先知道所有的山頂在哪邊才能去比較對吧?
那我們就先把問題拆成
Step1. 找到所有的小山頂
而我們要判斷是否為小山頂
其實就是不斷判斷兩兩相鄰的數是否由持續遞增轉成持續遞減

Step2. 找出最長的山

因為我們已經知道山頂不會在頭尾,所以我們要比較的數可以從第二個位置到陣列的倒數第二個位置
我們來隨便用個例子來走訪,這個例子的結果應該會是6,山形為 [ 0, 10, 7, 6, -1, -3]

arr = [1, 2, 4, 4, 5, 0, 10, 7, 6, -1, -3, 3, 4]

我們開始拿arr[1]=2和他前後的數做比較:
因為2 > 1,但 2!>4,所以2不是山頂,但我們不能確定他是否在要到山頂的路
略過中間重複的敘述,接著我們走到5,發現4 < 5,且5> 4,所以5是我們現在找到的第一個山頂

接著我們找到10為第二個山頂,最後結束所有的查詢,在這個過程中我們需要O(N)來完成

再來看我們要做的第二個問題,也就是找出最長的山。
我們可以把剛剛找出來的山頂,也就是5和10分別檢查它的左邊不斷嚴格遞減的長度,同理右邊也是找不斷嚴格遞減的長度。
第二步驟的時間複雜度,如果我們在第一個步驟完全沒有找到山頂,則這一步只用花O(1),因為不需要做任何事。但如果有的話,則需要O(N)。

不過,在下結論之前,我們先來想一件事。

我們是否一定得要把這兩個步驟順序完全拆開,用另一個空間來暫存我們找到的所有山頂?(如果最糟會需要O(N))

我們應該可以在找山頂的過程中,在找到的時後就開始頂執行第二個步驟,最後只需要額外儲存一個目前最大的長度即可,此外因為頂後面的部分應該是要嚴格遞減(下坡),所以不可能會是下一個山頂的上坡,那我們根本就可以跳過下坡的這些數直接開始找下一個山頂不是嗎?
以這種方式,整體的時間複雜度O(N),空間複雜度為O(1)

我們來實作吧!

var longestMountain = function (arr) {
  let longestLength = 0;
  let i = 1;
  while (i < arr.length - 1) {
    const isPeak = arr[i - 1] < arr[i] && arr[i + 1] < arr[i];
    if (!isPeak) {
      i++;
      continue;
    }

    let left = i - 2;
    while (left >= 0 && arr[left] < arr[left + 1]) {
      left--;
    }
    let right = i + 2;
    while (right < arr.length && arr[right] < arr[right - 1]) {
      right++;
    }

    const peakLength = right - left - 1;
    longestLength = Math.max(longestLength, peakLength);
    i = right;
  }
  return longestLength;
};

很多時候在想問題的時後會想把問題拆解,不過拆解完後也可以再思考看看,其實有些事情可以一氣喝成!

明日題目預告: Valid Palindrome


上一篇
Day 07 : Squares of a Sorted Array
下一篇
Day 09: Valid Palindrome
系列文
30天用JavaScript刷題刷起來!30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

1
TD
iT邦新手 4 級 ‧ 2021-09-23 23:35:03

這題好有趣啊!

0
TD
iT邦新手 4 級 ‧ 2021-09-23 23:35:50

再下結論之前

在 (?)

用另一個空間來暫存文我們找到的所有山頂

多了一個文?

Jen iT邦新手 5 級 ‧ 2021-09-23 23:55:40 檢舉

馬上修正 感謝!!/images/emoticon/emoticon41.gif

我要留言

立即登入留言